/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
// 1.使用qsort对结构体数组中的cnt进行排序
// 2.使用uthash

// typedef struct {
//     int num;
//     int cnt;
// } elem_t;

// int cmp_int(const void *a, const void *b) {
//     return *(int *)a - *(int *)b;
// }
// // 对结构体的中cnt降序排序
// int cmp_st(const void *a, const void *b) {
//     return (*(elem_t *)b).cnt - (*(elem_t *)a).cnt;
// }

// int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
//     qsort(nums, numsSize, sizeof(int), cmp_int);
//     elem_t arr[numsSize];   //结构体数组

//     //统计频次
//     int i, idx = 0;
//     arr[0].num = nums[0];
//     arr[0].cnt = 1;
//     for (i = 1; i < numsSize; i++) {
//         if (nums[i] == nums[i-1]) //重复元素
//             arr[idx].cnt++;
//         else {
//             arr[++idx].num = nums[i];
//             arr[idx].cnt = 1;
//         }
//     }
    

//     // 按什么排，怎么排序，取决于cmp函数
//     qsort(arr, idx + 1, sizeof(elem_t), cmp_st);
//     int *res = malloc(sizeof(int)*k);
//     for (i = 0; i < k; i++) {
//         res[i] = arr[i].num;
//     }
//     *returnSize = k;
//     return res;
// }



/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
typedef struct {
    int key;
    int cnt;
    UT_hash_handle hh;
} uthash_t;

int cmp_func(const void *a, const void *b) {
    return ((uthash_t *)b)->cnt - ((uthash_t *)a)->cnt; //降序
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    int i;
    uthash_t *hash = NULL, *ret = NULL;

    for (i = 0; i < numsSize; i++) {
        //int value = nums[i];
        HASH_FIND_INT(hash, &nums[i], ret);
        if (ret == NULL) {//not found
            uthash_t *temp = malloc(sizeof(uthash_t));
            temp->key = nums[i];
            temp->cnt = 1;
            HASH_ADD_INT(hash, key, temp);
        } else {
            ret->cnt++;
        }
    }

    int *res = malloc(sizeof(int)*k);
    HASH_SORT(hash, cmp_func);
    for (i = 0; i < k; i++)  {
        res[i] = hash->key;
        hash = hash->hh.next;
    }

    *returnSize = k;
    return res;
}